/*************************************************************
*
* cgm_search.cpp
*  binary searches on the array without direct sorting
*************************************************************/
#include <m3d/m3d_stdafx.h>

#include <math.h>
#include <stdio.h>
#include <stdlib.h>

#include <ap_comm.h>

#include <m3d.h>
#include <cgm.h>

//
// Static functions
//

//
// Static variables
//
static osLOCK     _cgmSearchLock("_cgmSearchLock");
//static apDECL(osLOCK, _cgmSearchLock, 8);

static cgmSEARCH  *_cgmSearchPtr;


/*************************************************************
* cgmSEARCH Class members
**************************************************************/
cgmSEARCH::~cgmSEARCH (void)
{
   if (state.Is(CGM_ST_SEARCH_SORTED_LIST_ALLOCATED)) {
      delete [] itemIndSorted;
      itemIndSorted = NULL;
      state.Clear(CGM_ST_SEARCH_SORTED_LIST_ALLOCATED);
   }
}

/*************************************************************
* cgmSEARCH::Init ()
*   Initializes binary search 
* IN  : nItems   - number of items in array
*       itemSize - size of item
*       itemList - list of items
* OUT : none
* RET : FALSE if an error occured
**************************************************************/
BOOL cgmSEARCH::Init (int _nItems, int _itemSize, void *_itemList, int *_itemIndSorted)
{
   int i;

   itemSize = _itemSize;
   itemList = _itemList;
   nItems   = _nItems;

   if (_itemIndSorted == 0) {
      ASSERT(!state.Is(CGM_ST_SEARCH_SORTED_LIST_ALLOCATED));
      if ((itemIndSorted = apNEW int[nItems]) == NULL) {
         return FALSE;
      }
      state.Set(CGM_ST_SEARCH_SORTED_LIST_ALLOCATED);
   } else {
      ASSERT(itemIndSorted == NULL || !state.Is(CGM_ST_SEARCH_SORTED_LIST_ALLOCATED));
      itemIndSorted = _itemIndSorted;
   }
   for (i = 0; i < nItems; i ++) {
      itemIndSorted[i] = i;
   }
   _cgmSearchLock.Lock();
   _cgmSearchPtr = this;
   qsort(itemIndSorted, nItems, sizeof(int), QSortCB);
   _cgmSearchPtr = NULL;
   _cgmSearchLock.Unlock();
   return TRUE;
}

/*************************************************************
* cgmSEARCH::Search ()
*    Searchs for an element using binary search
* IN  : pItemSearch - pointer to item to be searched for
*       cmpMode     - comparation mode (CGM_SEARCH_LESS, CGM_SEARCH_GREATER)
* RET : index of found element or -1 if element not found
**************************************************************/
int cgmSEARCH::Search (void *pItemSearch, int cmpMode)
{
   int firstInd = 0;
   int lastInd  = nItems-1;

   while (lastInd - firstInd > 1) {
      int ind   = (firstInd + lastInd) / 2;
      void * pItem = GetItemCmpPtrInd(ind);
   
      int cmpRes = CmpItem(pItem, pItemSearch);
      if (cmpMode == CGM_SEARCH_EQUAL || cmpMode == CGM_SEARCH_LESS) {
         if (cmpRes < 0) {
            firstInd = ind;
         } else {
            lastInd  = ind;
         } 
      } else if (cmpMode == CGM_SEARCH_GREATER) {
         if (cmpRes > 0) {
            lastInd  = ind;
         } else {
            firstInd = ind;
         } 
      }
   }

   switch (cmpMode) {
      case CGM_SEARCH_EQUAL:
         if (CmpItem(GetItemCmpPtrInd(firstInd), pItemSearch) == 0) {
            return firstInd;
         }
         if (CmpItem(GetItemCmpPtrInd(lastInd), pItemSearch) == 0) {
            return lastInd;
         }
         return -1;

      case CGM_SEARCH_LESS:
         return firstInd;

      case CGM_SEARCH_GREATER:
         return lastInd;

      default:
         STRONG_ASSERT(!"Unknown cmpMode value");
         return -1;
   }
}

/*************************************************************
* cgmSEARCH::Term ()
*    Term search 
**************************************************************/
void cgmSEARCH::Term (void)
{
   if (state.Is(CGM_ST_SEARCH_SORTED_LIST_ALLOCATED)) {
      delete [] itemIndSorted;
      state.Clear(CGM_ST_SEARCH_SORTED_LIST_ALLOCATED);
   }
   itemIndSorted = NULL;
   nItems   = 0;
   itemSize = -1;
   itemList = NULL;
   return;
}
/*************************************************************
* cgmSEARCH_VLIST Class members
**************************************************************/
/*************************************************************
* cgmSEARCH_VLIST::Init ()
*   Initializes search in vertex array
* IN  : nItems   - number of items in array
*       itemSize - size of item
*       itemList - list of items
* OUT : none
* RET : FALSE if an error occured
**************************************************************/
BOOL cgmSEARCH_VLIST::Init (int _nItems, int _itemSize, void *_itemList, int *_itemIndSorted)
{
   if (dim == -1) {
      dim = _itemSize / sizeof(float);
   }
   ASSERT(dim <= CGM_MAX_DIM);

   float v[CGM_MAX_DIM];
   float bb_min[CGM_MAX_DIM];
   float bb_max[CGM_MAX_DIM];

   sortDir[0] = 1.0f;
   for (int j = 1; j < dim; j ++) {
      sortDir[j] = 0.0f;
   }

   if (_nItems > 1) {
      // clear AABB
      for (int j = 0; j < dim; j++) {
         bb_min[j] = 1e38f;
         bb_max[j] = -1e38f;
      }

      for (int i = 0; i < _nItems; i ++) {
         for (int j = 0; j < dim; j ++) {
            m3dVectComponent(&v, j) = m3dVectComponent((BYTE*)_itemList + i * _itemSize + offset, j);

            if (v[j] < bb_min[j]) {
               bb_min[j] = v[j];
            }
            if (v[j] > bb_max[j]) {
               bb_max[j] = v[j];
            }
         }
      }

      float fLen = 0.0f;
      for (int j = 0; j < dim; j ++) {
         sortDir[j] = bb_max[j] - bb_min[j];
         fLen += sortDir[j] * sortDir[j];
      }
      if (fLen > 1e-12f) {
         fLen = sqrt(fLen); // !!! looks like a bugfix
         for (int j = 0; j < dim; j ++) {
            sortDir[j] /= fLen;
         }
      }
   }

   float accuracyTmp = accuracy;
   accuracy    = 0.f;
   if (!cgmSEARCH::Init(_nItems, _itemSize, _itemList, _itemIndSorted)) {
      return FALSE;
   }
   accuracy = accuracyTmp;
   return TRUE;
}
/*************************************************************
* cgmSEARCH_VLIST::Term ()
*    Term search 
**************************************************************/
void cgmSEARCH_VLIST::Term (void)
{
   cgmSEARCH::Term();
   accuracy = 0.f;
   for (int j = 0; j < CGM_MAX_DIM; ++j) {
      sortDir[j] = 0.0f;
   }
}
/*************************************************************
* cgmSEARCH_VLIST::CmpItem ()
*   Compare two items (see qsort)
**************************************************************/
int cgmSEARCH_VLIST::CmpItem (void *pItem1, void *pItem2, float _accuracy)
{
   if (m3dIsZero(_accuracy)) {
      _accuracy = accuracy;
   }

   float prod1 = 0, prod2 = 0;
   for (int j = 0; j < dim; j ++) {
      prod1 += m3dVectComponent(&sortDir, j) *  m3dVectComponent(pItem1, j);
      prod2 += m3dVectComponent(&sortDir, j) *  m3dVectComponent(pItem2, j);
   }
   if (prod1 < prod2 - _accuracy) {
      return CGM_SEARCH_LESS;
   } else if (prod1 > prod2 + _accuracy) {
      return CGM_SEARCH_GREATER;
   }

   return CGM_SEARCH_EQUAL;
}
/*****************************************************
* cgmSEARCH_VLIST::Dist ()
*  
*****************************************************/
float cgmSEARCH_VLIST::Dist (void *pItem1, void *pItem2)
{
   float dist;
   int   j;

   dist = 0.f;
   for (j = 0; j < dim; j ++) {
      dist += m3dPow2(m3dVectComponent(pItem1, j) -  m3dVectComponent(pItem2, j));
   }

   return m3dSqrt(dist);
}
/*****************************************************
* cgmSEARCH_VLIST::DistSq ()
*  
*****************************************************/
float cgmSEARCH_VLIST::DistSq (void *pItem1, void *pItem2)
{
   float dist;
   int   j;

   dist = 0.f;
   for (j = 0; j < dim; j ++) {
      dist += m3dPow2(m3dVectComponent(pItem1, j) -  m3dVectComponent(pItem2, j));
   }

   return dist;
}
/*****************************************************
* cgmSEARCH_VLIST::Weld ()
*
*****************************************************/
int cgmSEARCH_VLIST::Weld (int *weldInd)
{
   int    i, j, nVertRes;
   int    firstInd, lastInd, ind;
   void  *pVert;
   float _accuracy = accuracy;
   float  accuracySq = accuracy * accuracy;
   float  dist;

   memset(weldInd, -1, nItems * sizeof(int));

   SetAccuracy(3.f * accuracy);
   nVertRes = 0;
   for (i = 0; i < nItems; i ++) {
      if (weldInd[i] != -1) {
         continue;
      }
      pVert = GetItemCmpPtr(i);

      firstInd = Search(pVert, CGM_SEARCH_LESS);
      lastInd  = Search(pVert, CGM_SEARCH_GREATER);

      // Find vertex with y coordinate exact v1.y
      for (j = firstInd; j <= lastInd; j ++) {
         ind = GetItemInd(j);

         dist = DistSq(pVert, GetItemCmpPtr(ind));
         if (i == ind || dist <= accuracySq) {
            weldInd[ind] = nVertRes;
         }
      }
      ASSERT(weldInd[i] != -1);
      nVertRes ++;
   }
   SetAccuracy(_accuracy);
   return nVertRes;
}
/*****************************************************
 * cgmSEARCH_VLIST::GetSameVert ()
 *    Find coincedent points 
 * IN:  nVert, vertList - finst point list
 * OUT: sameVertInd - for each vertex in first list index into
 *      second list or -1 if no coincidence was found
 * RET: number of councedent vertices
 *****************************************************/
int cgmSEARCH_VLIST::GetSameVert (int nVert, void *vertList, int *sameVertInd)
{
   int    i, j, k, nSameVert, vertInd;
   int    firstInd, lastInd, ind;
   float  dist, minDist;
   m3dV   vert;
   
   nSameVert = 0;
   for (i = 0; i < nVert; i ++) {
      vert = ((m3dV*)itemList)[i];

      firstInd = Search(&vert, CGM_SEARCH_LESS);
      lastInd  = Search(&vert, CGM_SEARCH_GREATER);

      // Find vertex with y coordinate exact v1.y
      vertInd = -1;
      minDist = M3D_INFINITY;
      for (j = firstInd; j <= lastInd; j ++) {
         ind  = GetItemInd(j);
         dist = 0.f;
         for (k = 0; k < dim; k ++) {         
            dist = max(dist, m3dFAbs(m3dVectComponent(GetItemCmpPtr(i), k) - m3dVectComponent(GetItemCmpPtr(ind), k)));
         }
         if (dist < minDist) {
            minDist = dist;
            vertInd = ind;
         }
      }
      if (minDist > accuracy) {
         sameVertInd[i] = -1;
      } else {
         sameVertInd[i] = vertInd;
         nSameVert ++;
      }
   }
   return nSameVert;
}

/*************************************************************
* cgmSEARCH_INT_LIST Class members
**************************************************************/
/*************************************************************
* cgmSEARCH_INT_LIST::CmpItem ()
*   Compare two items (see qsort)
**************************************************************/
int cgmSEARCH_INT_LIST::CmpItem (void *pItem1, void *pItem2, float _accuracy)
{
   int   diff = 0;
   
   switch (dim) {
      case 1:
         diff = *((char*)pItem1) - *((char*)pItem2);
         break;
      case 2:
         diff = *((short*)pItem1) - *((short*)pItem2);
         break;
      case 4:
         diff = *((int*)pItem1) - *((int*)pItem2);
         break;
   }
   if (diff < 0) {
      return CGM_SEARCH_LESS;
   } else if (diff > 0) {
      return CGM_SEARCH_GREATER;
   }
   return CGM_SEARCH_EQUAL;
}


/*****************************************************
* Static functions
*****************************************************/
/*****************************************************
* cgmSEARCH::QSortCB ()
*    Callback for QSORT functions
*****************************************************/
int __CDECL cgmSEARCH::QSortCB (const void *arg1, const void *arg2)
{
   void *pItem1, *pItem2;
   int   ind1, ind2;

   if (!_cgmSearchPtr) {
      ASSERT(0);
      *((BYTE*)0) = 0;
   }
   
   ind1   = *((int*)arg1);
   ind2   = *((int*)arg2);
   pItem1 = _cgmSearchPtr->GetItemCmpPtr(ind1);
   pItem2 = _cgmSearchPtr->GetItemCmpPtr(ind2);

   return _cgmSearchPtr->CmpItem(pItem1, pItem2);
}
//
// end of file "cgm_search.cpp"
//
